package leetcode.code0042;

import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution0042 implements IDebug {

//	n == height.length
//	1 <= n <= 2 * 104
//	0 <= height[i] <= 105

	public int trap(int[] height) {
		int n = height.length;
		if (n < 3) {// 两个桶边,装不了水
			return 0;
		}
		int ans = 0;// 总储水量
		Stack<Integer> s = new Stack<>();
		for (int i = 0; i < n; i++) {
			while (!s.isEmpty() && height[s.peek()] < height[i]) {
				int min = s.pop();// 当前位置桶底高度
				int r = i;// 右侧桶边脚标
				int l = s.isEmpty() ? -1 : s.peek();// 左侧桶边脚标,可能没有
				if (l != -1) {// 左侧没有比当前高的,当前位置不能接水,没有`左边`
					// 木桶短边 - 桶底高度 = 储水高度(Math.min(height[l], height[r]) - height[min])
					// 储水高度 * 桶底宽度 = 储水量 (r - l - 1)
					// 超过木桶短边短边的水,由两侧更高的桶边结算
					ans += (Math.min(height[l], height[r]) - height[min]) * (r - l - 1);
				}
			}
			s.add(i);
		}
		// 栈里的都是大高个,没有人能和他们配对接水,不用管,这里所有数字都找不到`右边`
		return ans;
	}

	@Override
	public void debug1() {
		String str = "[0,1,0,2,1,0,1,3,2,1,2,1]";
		int e = 6;
		int r = this.trap(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String str = "[4,2,0,3,2,5]";
		int e = 9;
		int r = this.trap(HelpDebug.str2array3(str));
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution0042 so = new Solution0042();
		so.debug1();
		so.debug2();
	}

}
